package com.tgy.algorithm.base.other;


public class _切最少刀变成回文串 {

    public static int minCutPalindrome(String content) {

        if (content == null || content.length() == 0) {
            return 0;
        }

//        [left,right]
        int len = content.length();
        boolean[][] cache = new boolean[len][len];
        char[] chars = content.toCharArray();
        for (int i = 0; i < len; i++) {
            cache[i][i] = true;
            if (i < len - 1) {
                cache[i][i+1] = (chars[i] == chars[i+1]);
            }
        }

        for (int i = len - 2; i >= 0; i--) {
            for (int j = i+2; j < len; j++) {
                cache[i][j] = (chars[i] == chars[j]) && cache[i+1][j-1];
            }
        }

        System.out.println("===========");
        return doMinCutPalindrome(chars, 0, cache);
    }

    public static int doMinCutPalindrome(char[] chars,int left,boolean[][] cache) {


        int len = chars.length;

        if (left >= len) {
            return 0;
        }

        int ret = len;
        for (int i = left; i < len ; i++) {
            if (cache[left][i]) {
                ret = Math.min(ret,doMinCutPalindrome(chars,i+1,cache) + 1);
            }
        }
        
        return ret;
    }


    public static int minCutPalindrome01(String content) {

        if (content == null || content.length() == 0) {
            return 0;
        }

//        [left,right]
        int len = content.length();
        boolean[][] cache = new boolean[len][len];
        char[] chars = content.toCharArray();
        for (int i = 0; i < len; i++) {
            cache[i][i] = true;
            if (i < len - 1) {
                cache[i][i+1] = (chars[i] == chars[i+1]);
            }
        }

        for (int i = len - 2; i >= 0; i--) {
            for (int j = i+2; j < len; j++) {
                cache[i][j] = (chars[i] == chars[j]) && cache[i+1][j-1];
            }
        }

        int[] dp = new int[len + 1];
        dp[len] = 0;
        for (int i = 0; i < len; i++) {
            dp[i] = len;
        }

        for (int i = len - 1; i >= 0; i--) {
            for (int j = i; j < len ; j++) {
                if (cache[i][j]) {
                    dp[i] = Math.min(dp[i],dp[j+1] + 1);
                }
            }
        }

        return dp[0];
    }

    public static void main(String[] args) {
        String content = "cbcaba";
        /**
         *      a b c c b a
         *    a T F F F F T
         *    b   T F F T F
         *    c     T T F F
         *    c       T F F
         *    b         T F
         *    a           T
         *
         */
//        int min = minCutPalindrome(content);
        int min = minCutPalindrome01(content);
        System.out.println(min);
    }
}
